RCS "$Id: SortedList.sig,v 1.9 1998/08/13 11:35:08 pxs Exp $";
(******************************** SortedList *********************************)
(*                                                                           *)
(* DEPRECATED. It's very easy to produce very hard to find bugs using SL.    *)
(* Use inside small pieces of code if you must, but don't export or import   *)
(* un-type-checked reliance on things being sorted.                          *)
(*                                                                           *)
(*  Operations on sorted lists.                                              *)
(*                                                                           *)
(*  Most functions take a reflexive ANTISYMMETRIC ordering relation.         *)
(*  Some functions take a boolean which is true if duplicates are deleted.   *)
(*  Function add replaces an existing element if duplicates are deleted.     *)
(*  Function sort is stable -- the order of equal elements is maintained if  *)
(*  duplicates are not deleted; otherwise the first element is kept.         *)
(*                                                                           *)
(*****************************************************************************)

signature SORTEDLIST =
sig
   exception Retrieve

   val member   : ('a * 'a -> bool) -> 'a * 'a list -> bool
(* is the list sorted according to the predicate? *)
   val isSorted : ('a * 'a -> bool) -> 'a list -> bool
(* is the first list a sublist of the second? *)
   val sublist  : ('a * 'a -> bool) -> 'a list * 'a list -> bool
   val le       : ('a * 'a -> bool) -> 'a list * 'a list -> bool
(* the booleans here are true iff you want duplicates deleted *)
   val sort     : ('a * 'a -> bool) -> bool -> 'a list -> 'a list
   val add      : ('a * 'a -> bool) -> bool -> 'a * 'a list -> 'a list
   val merge    : ('a * 'a -> bool) -> bool -> 'a list * 'a list -> 'a list
(* like merge, but if an elt appears in both lists the fn "merges" those *)
(* elts. Care: The "merged" elt is left in the same place in the list.   *)
(* So this will be pointless if the ordering really is antisymmetric...  *)
   val merge1     : ('a * 'a -> bool) -> ('a * 'a -> 'a) ->
     'a list * 'a list -> 'a list
(* The 'a lists have to be sorted, but you can give _them_ in any order. *)
   val bigmerge : ('a * 'a -> bool) -> bool -> 'a list list -> 'a list
   val inter    : ('a * 'a -> bool) -> 'a list * 'a list -> 'a list
(* The 'b list doesn't have to be sorted, but the 'a list will be *)
   val map : ('a * 'a -> bool) -> bool -> ('b -> 'a) -> 'b list -> 'a list
     
(* These functions key: 'a -> 'k are used to turn list elements into the  *)
(* things we want to compare. When you apply the fn to the 'a list,  *)
(* you'd better get a list sorted by the 'k * 'k -> bool function!   *)
(* The idea is that lists to which these fns are applied should be sorted *)
(* by these key values. There's a widespread assumption that keys are unique.*)

(* get the 'a elt which codes to given 'k value; raise Retrieve if none *)
   val retrieve : ('a -> 'k) -> ('k * 'k -> bool) -> 'k * 'a list -> 'a

(* use update and updateAdd with care: see code for assumptions made.   *)
   val update     : ('a -> 'k) -> ('k * 'k -> bool) -> ('a -> 'a) ->
     'k * 'a list -> 'a list
     
   val updateAdd : ('a -> 'k) -> ('k * 'k -> bool) -> 'a -> ('a -> 'a) ->
     'k * 'a list -> 'a list

(* this one removes all elts that code to k, doesn't assume unique keys *)
   val remove   : ('a -> 'k) -> ('k * 'k -> bool) -> 'k * 'a list -> 'a list
   val del_dups : ('a * 'a -> bool) -> 'a list -> 'a list
(* remove all the elements that code to anything on the key list. *)
(* 'k list must be sorted by 'k * 'k -> bool, 'a list by that o 'a->'k*)
   val minus : ('a -> 'k) -> ('k * 'k -> bool) -> 'a list * 'k list -> 'a list
end

